Application of RAGA based on SA in calculating critical water depth of open channel.

Superseding Nearest Neighbor Search on Uncertain Spatial Databases.
This paper proposes a new problem, called superseding nearest neighbor search, on uncertain spatial databases, where each object is described by a multidimensional probability density function. Given a query point q, an object is a nearest neighbor (NN) candidate if it has a non-zero probability to be the NN of q. Given two NN candidates o1 and o2, o1 supersedes o2 if o1 is more likely to be closer to q. An object is a superseding nearest neighbor (SNN) of q, if it supersedes all the other NN-candidates. Sometimes no object is able to supersede every other NN candidate. In this case, we return the SNNcore — the minimum set of NN-candidates each of which supersedes all the NN-candidates outside the SNN-core. Intuitively, the SNN-core contains the best objects, because any object outside the SNN-core is worse than all the objects in the SNN-core. We show that the SNN-core can be efficiently computed by utilizing a conventional multidimensional index, as confirmed by extensive experiments.
Incremental and General Evaluation of Reverse Nearest Neighbors.
This paper presents a novel algorithm for Incremental and General Evaluation of continuous Reverse Nearest neighbor queries (IGERN, for short). The IGERN algorithm is general in that it is applicable for both continuous monochromatic and bichromatic reverse nearest neighbor queries. This problem is faced in a number of applications such as enhanced 911 services and in army strategic planning. A main challenge in these problems is to maintain the most up to date query answers as the dataset frequently changes over time. Previous algorithms for monochromatic continuous reverse nearest neighbor queries rely mainly on monitoring at the worst case of six pie regions, whereas IGERN takes a radical approach by monitoring only a single region around the query object. The IGERN algorithm clearly outperforms the state-of-the-art algorithms in monochromatic queries. We also propose a new optimization for the monochromatic IGERN to reduce the number of nearest neighbor searches. Furthermore, a filter and refine approach for IGERN (FR-IGERN) is proposed for the continuous evaluation of bichromatic reverse nearest neighbor queries which is an optimized version of our previous approach. The computational complexity of IGERN and FR-IGERN is presented in comparison to the state-of-the-art algorithms in the monochromatic and bichromatic cases. In addition, the correctness of IGERN and FR-IGERN in both the monochromatic and bichromatic cases respectively are proved. Extensive experimental analysis using synthetic and real datasets shows that IGERN and FR-IGERN is efficient, is scalable, and outperforms previous techniques for continuous reverse nearest neighbor queries.


Workload%2DDriven Compressed Skycube Queries in Wireless Applications.

Extendible Hashing.

Hash%2Dbased Indexing.
In this paper, we present two novel hash-based indexing structures, based on Bloom filters, called Breadth and Depth Bloom filters, which in contrast to traditional hash-based indexes, are able to summarize hierarchical data and support regular path expression queries. We describe how these structures can be used for resource discovery in peer-to-peer networks. We have implemented both structures and our experiments show that they both outperform Simple Bloom filters in discovering the appropriate resources. 1.
I%2FO Model of Computation.
In the design of algorithms for large-scale applications it is essential to consider the problem of minimizing I/O communication. Geographical information systems (GIS) are good examples of such large-scale applications as they frequently handle huge amounts of spatial data. In this paper we develop efficient external-memory algorithms for a number of important problems involving line segments in the plane, including trapezoid decomposition, batched planar point location, triangulation, red–blue line segment intersection reporting, and general line segment intersection reporting. In GIS systems the first three problems are useful for rendering and modeling, and the latter two are frequently used for overlaying maps and extracting information from them. 
Linear Hashing.
Consider the set H of all linear (or affine) transformations between two vector spaces over a finite field F . We study how good H is as a class of hash functions, namely we consider hashing a set S of size n into a range having the same cardinality n by a randomly chosen function from H and look at the expected size of the largest hash bucket. H is a universal class of hash functions for any finite field, but with respect to our measure different fields behave differently. If the finite field F has n elements then there is a bad set S ae F  2  of size n with expected maximal bucket size\Omega\Gamma  n  1=3  ). If n is a perfect square then there is even a bad set with largest bucket size always at least  p  n. (This is worst possible, since with respect to a universal class of hash functions every set of size n has expected largest bucket size below  p  n + 1=2.) If, however, we consider the field of two elements then we get much better bounds. The best previously known upper bound on...
B %2DTree.
B-trees have become, de facto, a standard for file organization. File indexes of users, dedicated database systems, and general-purpose access methods have all been proposed and nnplemented using B-trees This paper reviews B-trees and shows why they have been so successful It discusses the major variations of the B-tree, especially the B+-tree,

Resource Allocation Problems in Spatial Databases.


ANGEL Enhancing the Utility of Generalization for Privacy Preserving Publication.
Generalization is a well-known method for privacy preserving data publication. Despite its vast popularity, it has several drawbacks such as heavy information loss, difficulty of supporting marginal publication, and so on. To overcome these drawbacks, we develop ANGEL 1, a new anonymization technique that is as effective as generalization in privacy protection, but is able to retain significantly more information in the microdata. ANGEL is applicable to any monotonic principles (e.g., l-diversity, t-closeness, etc.), with its superiority (in correlation preservation) especially obvious when tight privacy control must be enforced. We show that ANGEL lends itself elegantly to the hard problem of marginal publication. In particular, unlike generalization that can release only restricted marginals, our technique can be easily used to publish any marginals with strong privacy guarantees.
ANGEL Enhancing the Utility of Generalization for Privacy Preserving Publication.
Generalization is a well-known method for privacy preserving data publication. Despite its vast popularity, it has several drawbacks such as heavy information loss, difficulty of supporting marginal publication, and so on. To overcome these drawbacks, we develop ANGEL 1, a new anonymization technique that is as effective as generalization in privacy protection, but is able to retain significantly more information in the microdata. ANGEL is applicable to any monotonic principles (e.g., l-diversity, t-closeness, etc.), with its superiority (in correlation preservation) especially obvious when tight privacy control must be enforced. We show that ANGEL lends itself elegantly to the hard problem of marginal publication. In particular, unlike generalization that can release only restricted marginals, our technique can be easily used to publish any marginals with strong privacy guarantees.
On continuously monitoring the top%2Dk moving objects with relational group and score functions.
ACM SIGSPATIAL addresses issues related to the acquisition, management, and processing of spatially-related information with a focus on algorithmic, geometric, and visual considerations. The scope includes, but is not limited to, geographic information systems. Current ACM SIGSPATIAL officers are:
On Skylining with Flexible Dominance Relation.
Abstract — Given a set of d dimensional objects, a skyline query finds the objects (“skyline”) that are not dominated by others. However, skylines do not always provide useful query results to users, and existing methods of various skyline queries have at least one of the following drawbacks: (1) the size of skyline objects can not be controlled, or can be only increased or only decreased but not both; (2) skyline objects do not have built-in ranks; (3) skylines do not reflect users ’ weights (preferences) at different dimensions. In this paper, we propose a unified approach, the ε-skyline, to effectively solve all three drawbacks. We explore the properties of ε-skylines and propose several different algorithms to compute ε-skylines. I.
On Monitoring the top%2Dk Unsafe Places.
ACM SIGSPATIAL addresses issues related to the acquisition, management, and processing of spatially-related information with a focus on algorithmic, geometric, and visual considerations. The scope includes, but is not limited to, geographic information systems. Current ACM SIGSPATIAL officers are:
On Anti%2DCorruption Privacy Preserving Publication.
Abstract — This paper deals with a new type of privacy threat, called “corruption”, in anonymized data publication. Specifically, an adversary is said to have corrupted some individuals, if s/he has already obtained their sensitive values before consulting the released information. Conventional generalization may lead to severe privacy disclosure in the presence of corruption. Motivated by this, we advocate an alternative anonymization technique that integrates generalization with perturbation and stratified sampling. The integration provides strong privacy guarantees, even if an adversary has corrupted any number of individuals. We verify the effectiveness of the proposed technique through experiments with real data. I.
Aggregation Query%2C Spatial.

Fastest%2DPath Computation.
Efficient fastest path computation in the presence of varying speed conditions on a large scale road network is an essential problem in modern navigation systems. Factors affecting road speed, such as weather, time of day, and vehicle type, need to be considered in order to select fast routes that match current driving conditions. Most existing systems compute fastest paths based on road Euclidean distance and a small set of predefined road speeds. However, “History is often the best teacher”. Historical traffic data or driving patterns are often more useful than the simple Euclidean distance-based computation because people must have good reasons to choose these routes, e.g., they may want to avoid those that pass through high crime areas at night or that likely encounter accidents, road construction, or traffic jams. In this paper, we present an adaptive fastest path algorithm capable of efficiently accounting for important driving and speed patterns mined from a large set of traffic data. The algorithm is based on the following observations: (1) The hierarchy of roads can be used to partition the road network into areas, and different path pre-computation strategies can be used at the area level, (2) we can limit our route search strategy to edges and path segments that are actually frequently traveled in the data, and (3) drivers usually traverse the road network through the largest roads available given the distance of the trip, except if there are small roads with a significant speed advantage over the large ones. Through an extensive experimental evaluation on real road networks we show that our algorithm provides desirable (short and well-supported) routes, and that it is significantly faster than competing methods.
On computing temporal aggregates with range predicates.
A temporal aggregation query is an important but costly operation for applications that maintain timeevolving  data (data warehouses, temporal databases, etc.). Due to the large volume of such data, performance  improvements for temporal aggregation queries are critical. In this paper we examine techniques to compute  temporal aggregates that include key-range predicates (range temporal aggregates). In particular we concentrate  on SUM, COUNT and AVG aggregates. This problem is novel; to handle arbitrary key ranges, previous  methods would need to keep a separate index for every possible key range. We propose an approach based  on a new index structure called the Multiversion SB-Tree, which incorporates features from both the SB-Tree  and the Multiversion B-Tree, to handle arbitrary key-range temporal SUM, COUNT and AVG queries. We  analyze the performance of our approach and present experimental results that show its efficiency.  1 
Mining Frequent Generalized Itemsets and Generalized Association Rules Without Redundancy.

QueryScope visualizing queries for repeatable database tuning.
“To understand is to perceive patterns. ”  — Isaiah Berlin Reading and perceiving complex SQL queries has been a time consuming task in traditional database applications for decades. When it comes to decision support systems with automatically generated and sometimes highly nested SQL queries, human understanding or tuning of these workloads becomes even more challenging. This demonstration explores visualization methods to represent queries as graphs. We developed the QueryScope tool to help visualize and understand critical elements of a query, thereby cutting down the learning curve. We show how the tool allows the user to drill down on particular queries or to find similarly structured queries that may exhibit similar tuning opportunities. The queries shown in the demonstration are taken from real tuning engagements. 1.
Advances in Spatial and Temporal Databases
We present here a theory of motion from a topological point of view, in a symbolic perspective. Taking space-time histories of objects as primitive entities, we introduce temporal and topological relations on the thus defined space-time to characterize classes of spatial changes. The theory thus accounts for qualitative spatial information, dealing with underspecified, symbolic information when accurate data is not available or unnecessary. We show that these structures give a basis for commonsense spatio-temporal reasoning by presenting a number of significant deductions in the theory. This can serve as a formal basis for languages describing motion events in a qualitative way.
Continuous Evaluation of Monochromatic and Bichromatic Reverse Nearest Neighbors.
This paper presents a novel algorithm for Incremental and General Evaluation of continuous Reverse Nearest neighbor queries (IGERN, for short). The IGERN algorithm is general as it is applicable for both the monochromatic and bichromatic reverse nearest neighbor queries. The incremental aspect of IGERN is achieved through determining only a small set of objects to be monitored. While previous algorithms for monochromatic queries rely mainly on monitoring six pie regions, IGERN takes a radical approach by monitoring only a single region around the query object. The IGERN algorithm clearly outperforms the state-of-theart algorithms in monochromatic queries. In addition, the IGERN algorithm presents the first attempt for continuous evaluation of bichromatic reverse nearest neighbor queries. The computational complexity of IGERN is presented in comparison to the state-of-the-art algorithms in the monochromatic case and to the use of Voronoi diagrams for the bichromatic case. In addition, the correctness of IGERN in both the monochromatic and bichromatic cases are proved. Extensive experimental analysis shows that IGERN is efficient, is scalable, and outperforms previous techniques for continuous reverse nearest neighbor queries. 1
On Multidimensional k%2DAnonymity with Local Recoding Generalization.
This paper presents the first theoretical study, on using local-recoding generalization (LRG) to compute a kanonymous table with quality guarantee. First, we prove that it is NP-hard both to find the table with the maximum quality, and to discover a solution with an approximation ratio at most 5/4. Then, we develop an algorithm with good balance between the approximation ratio and time complexity. The quality of our solution is verified by experiments. 1
Continuous Evaluation of Monochromatic and Bichromatic Reverse Nearest Neighbors.
This paper presents a novel algorithm for Incremental and General Evaluation of continuous Reverse Nearest neighbor queries (IGERN, for short). The IGERN algorithm is general as it is applicable for both the monochromatic and bichromatic reverse nearest neighbor queries. The incremental aspect of IGERN is achieved through determining only a small set of objects to be monitored. While previous algorithms for monochromatic queries rely mainly on monitoring six pie regions, IGERN takes a radical approach by monitoring only a single region around the query object. The IGERN algorithm clearly outperforms the state-of-theart algorithms in monochromatic queries. In addition, the IGERN algorithm presents the first attempt for continuous evaluation of bichromatic reverse nearest neighbor queries. The computational complexity of IGERN is presented in comparison to the state-of-the-art algorithms in the monochromatic case and to the use of Voronoi diagrams for the bichromatic case. In addition, the correctness of IGERN in both the monochromatic and bichromatic cases are proved. Extensive experimental analysis shows that IGERN is efficient, is scalable, and outperforms previous techniques for continuous reverse nearest neighbor queries. 1
Efficient mining of max frequent patterns in a generalized environment.
This poster paper summarizes our solution for mining max frequent generalized itemsets (g-itemsets), a compact representation for frequent patterns in the generalized environment. Categories and Subject Descriptors: H.m Information
Finding Fastest Paths on A Road Network with Speed Patterns.
This paper proposes and solves the Time-Interval All Fastest Path (allFP) query. Given a user-defined leaving or arrival time interval I, a source node s and an end node e, allFP asks for a set of all fastest paths from s to e, one for each sub-interval of I. Note that the query algorithm should find a partitioning of I into sub-intervals. Existing methods can only be used to solve a very special case of the problem, when the leaving time is a single time instant. A straightforward solution to the allFP query is to run existing methods many times, once for every time instant in I. This paper proposes a solution based on novel extensions to the A * algorithm. Instead of expanding the network many times, we expand once. The travel time on a path is kept as a function of leaving time. Methods to combine travel-time functions are provided to expand a path. A novel lower-bound estimator for travel time is proposed. Performance results reveal that our method is more efficient and more accurate than the discrete-time approach. 1
Continuous Reverse Nearest Neighbor Monitoring.
In this paper, we study the problem of continuous monitoring of reverse k nearest neighbor queries. Existing continuous reverse nearest neighbor monitoring techniques are sensitive towards objects and queries movement. For example, the results of a query are to be recomputed whenever the query changes its location. We present a framework for continuous reverse k nearest neighbor queries by assigning each object and query with a rectangular safe region such that the expensive recomputation is not required as long as the query and objects remain in their respective safe regions. This significantly improves the computation cost. As a by-product, our framework also reduces the communication cost in client-server architectures because an object does not report its location to the server unless it leaves its safe region or the server sends a location update request. We also conduct a rigid cost analysis to guide an effective selection of such rectangular safe regions. The extensive experiments demonstrate that our techniques outperform the existing techniques by an order of magnitude in terms of computation cost and communication cost. 1.
Refreshing the sky the compressed skycube with efficient support for frequent updates.
The skyline query is important in many applications such as multi-criteria decision making, data mining, and userpreference queries. Given a set of d-dimensional objects, the skyline query finds the objects that are not dominated by others. In practice, different users may be interested in different dimensions of the data, and issue queries on any subset of d dimensions. This paper focuses on supporting concurrent and unpredictable subspace skyline queries in frequent updated databases. Simply to compute and store the skyline objects of every subspace in a skycube will incur expensive update cost. In this paper, we investigate the important issue of updating the skycube in a dynamic environment. To balance the query cost and update cost, we propose a new structure, the compressed skycube, which concisely represents the complete skycube. We thoroughly explore the properties of the compressed skycube and provide an efficient object-aware update scheme. Experimental results show that the compressed skycube is both query and update efficient. 1.
Progressive Computation of the Min%2DDist Optimal%2DLocation Query.
This paper proposes and solves the min-dist optimal-location query in spatial databases. Given a set S of sites, a set O of weighted objects, and a spatial region Q, the min-dist optimal-location query returns a location in Q which, if a new site is built there, minimizes the average distance from each object to its closest site. This query can help a franchise (e.g. McDonald’s) decide where to put a new store in order to maximize the benefit to its customers. To solve this problem is challenging, for there are theoretically infinite number of locations in Q, all of which could be candidates. This paper first provides a theorem that limits the number of candidate locations without losing the power to find exact answers. Then it provides a progressive algorithm that quickly suggests a location, tells the maximum error it may have, and keeps refining the result. When the algorithm finishes, the exact answer can be found. The intermediate result of early runs can be used to prune the search space for later runs. Crucial to the pruning technique are novel lower-bound estimators. The proposed algorithm, the effect of several optimizations, and the progressiveness are experimentally evaluated. 1.
Supporting complex queries on multiversion XML documents.
Managing multiple versions of XML documents represents a critical requirement for many applications. Recently, there has been much work on supporting complex queries on XML data (e.g., regular path expressions, structural projections, etc.). In this paper, we examine the problem of implementing efficiently such complex queries on multiversion XML documents. Our approach relies on a numbering scheme whereby durable node numbers (DNNs) are used to preserve the order among the nodes of the XML tree while remaining invariant with respect to updates. Using the document’s DNNs, we show that many complex queries are reduced to combinations of range version retrieval queries. We thus examine three alternative storage organizations/indexing schemes to efficiently evaluate range version retrieval queries in this environment. A thorough performance analysis is then presented to reveal the advantages of each scheme.
Supporting complex queries on multiversion XML documents.
Managing multiple versions of XML documents represents a critical requirement for many applications. Recently, there has been much work on supporting complex queries on XML data (e.g., regular path expressions, structural projections, etc.). In this paper, we examine the problem of implementing efficiently such complex queries on multiversion XML documents. Our approach relies on a numbering scheme whereby durable node numbers (DNNs) are used to preserve the order among the nodes of the XML tree while remaining invariant with respect to updates. Using the document’s DNNs, we show that many complex queries are reduced to combinations of range version retrieval queries. We thus examine three alternative storage organizations/indexing schemes to efficiently evaluate range version retrieval queries in this environment. A thorough performance analysis is then presented to reveal the advantages of each scheme.
Improving the R%2A%2Dtree with outlier handling techniques.
The R*-tree, as a state-of-the-art spatial index, has already found its way into commercial systems like Oracle. In this paper, we aim at improving query performance of the R*tree. We focus on five widely used spatial queries: range query, aggregation query, nearest neighbor query, skyline query, and join query. The idea is to store outlier objects in internal tree nodes. The new structure is named the R O-tree. Here an outlier is an object which is located far from other objects or has large extent (we consider both point objects and objects with extent). If such objects are stored at higher levels of the tree, the lower-level nodes have smaller minimum bounding rectangles and thus the index performs better. To support the dynamic nature of the index, several structural and algorithmic changes are needed. The paper discusses these changes. In particular, we show how to identify and handle the outlier objects during page overflow/underflow, using gain/loss metrics. Extensive experiments reveal that the R O-tree significantly outperforms the R*-tree for all the five queries.
Close pair queries in moving object databases.
Databases of moving objects are important for air traffic control, ground traffic, and battlefield configurations. We introduce the (historical and spatial) range close-pair query for moving objects as an important problem for such databases. The purpose of a range close-pair query for moving objects is to find pairs of objects that were closer than ɛ during time interval I and within spatial range R, where ɛ, I and R are user-specified parameters. This paper solves the range close-pair query using two components: the retrieval component and the close-pair identification component. The retrieval component breaks up long trajectories into trajectory segments, which are produced in increasing time order, without the need for sorting. The retrieval component takes advantage of a new index mechanism, the Multiple TSB-tree. The segments are then pipelined to the close-pair identification component. The identification component introduces a novel spatial sweep that sweeps by time and one spatial dimension at the same time. Extensive experimental results are provided, demonstrating the advantages of the new approach when considering close pairs.
The Optimal%2DLocation Query.
This paper proposes and solves the min-dist optimal-location query in spatial databases. Given a set S of sites, a set O of weighted objects, and a spatial region Q, the min-dist optimal-location query returns a location in Q which, if a new site is built there, minimizes the average distance from each object to its closest site. This query can help a franchise (e.g. McDonald’s) decide where to put a new store in order to maximize the benefit to its customers. To solve this problem is challenging, for there are theoretically infinite number of locations in Q, all of which could be candidates. This paper first provides a theorem that limits the number of candidate locations without losing the power to find exact answers. Then it provides a progressive algorithm that quickly suggests a location, tells the maximum error it may have, and keeps refining the result. When the algorithm finishes, the exact answer can be found. The intermediate result of early runs can be used to prune the search space for later runs. Crucial to the pruning technique are novel lower-bound estimators. The proposed algorithm, the effect of several optimizations, and the progressiveness are experimentally evaluated. 1.
On Computing Top%2Dt Most Influential Spatial Sites.
Given a set O of weighted objects, a set S of  sites, and a query site s, the bichromatic RNN  query computes the influence set of s, or the  set of objects in O that consider s as the nearest  site among all sites in S. The influence of  a site s can be defined as the total weight of  its RNNs. This paper addresses the new and  interesting problem of finding the top-t most  influential sites from S, inside a given spatial  region Q. A straightforward approach is to  find the sites in Q, and compute the RNNs  of every such site. This approach is not efficient for two reasons. First, all sites in Q need  to be identified whatsoever, and the number  may be large. Second, both the site R-tree  and the object R-tree need to be browsed a  large number of times. For each site in Q, the  R-tree of sites is browsed to identify the influence  region -- a polygonal region that may  contain RNNs, and then the R-tree of objects  is browsed to find the RNN set. This paper  proposes an algorithm called TopInfluentialSites,  which finds the top-t most influential  sites by browsing both trees once systematically. Novel pruning
Optimizing spatial Min%2FMax aggregations.

Online Event%2Ddriven Subsequence Matching over Financial Data Streams.

A novel improvement to the R%2A%2Dtree spatial index using gain%2Floss metrics.

Online Event%2Ddriven Subsequence Matching over Financial Data Streams.

On Spatial%2DRange Closest%2DPair Query.
Abstract. An important query for spatial database research is to find the closest pair of objects in a given space. Existing work assumes two objects of the closest pair come from two different data sets indexed by R-trees. The closest pair in the whole space will be found via an optimzed R-tree join technique. However, this technique doesn’t perform well when the two data sets are identical. And it doesn’t work when the search range is some area other than the whole space. In this paper, we address the closest pair problem within the same data set. Further more, we propose a practical extension to the closest pair problem to involve a query range. The problem now becomes finding the closest pair of objects among those inside a given range. After extending the existing techniques to solve the new problem, we proposed two index structures based on augmenting the R-tree and we also give algorithms for maintaining these structrures. Experimental results show that our structures are more robust than earlier approaches. 1
Temporal and spatio%2Dtemporal aggregations over data streams using multiple time granularities.
Temporal and Spatio-Temporal Aggregations are... In this paper we examine the problem of computing such aggregates over data streams. The aggregates are maintained using multiple levels of temporal granularities: older data is aggregated using coarser granularities while more recent data is aggregated with finer detail. We present specialized indexing schemes for dynamically and progressively maintaining temporal and spatio-temporal aggregates. Moreover, these schemes can be parameterized. The levels of granularity as well as their corresponding index sizes (or validity lengths) can be dynamically adjusted. This provides a useful trade-off between aggregation detail and storage space. Analytical and experimental results show the efficiency of the proposed structures. We first address the temporal aggregation problem. A general framework of aggregating at multiple time granularities is then proposed. Finally we show how to utilize this framework to solve the range temporal and spatio-temporal aggregation problems.
Recent Progress on Selected Topics in Database Research %2D A Report by Nine Young Chinese Researchers Working in the United States.

Efficient Complex Query Support for Multiversion XML Documents.
Managing multiple versions of XML documents represents a critical requirement for many applications. Also, there has been much recent interest in supporting complex queries on XML data (e.g., regular path expressions, structural projections, DIFF queries). In this paper, we examine the problem of supporting efficiently complex queries on multiversioned XML documents. Our approach relies on a scheme based on durable node numbers (DNNs) that preserve the order among the XML tree nodes and are invariant with respect to updates. Using the document&#039;s DNNs various complex queries are reduced to combinations partial versio retrieval queries. We examine three indexing schemes to efficiently evaluate partial version retrieval queries in this environment. A thorough performance analysis is then presented to reveal the advantages of each scheme.
Temporal Aggregation over Data Streams Using Multiple Granularities.
Temporal aggregation is an important but costly operation for applications that maintain time-evolving data (data warehouses, temporal databases, etc.). In this paper we examine the problem of computing temporal aggregates over data streams. Such aggregates are maintained using multiple levels of temporal granularities: older data is aggregated using coarser granularities while more recent data is aggregated with finer detail. We present specialized indexing schemes for dynamically and progressively maintaining temporal aggregates.
Advance Database Aggregation Query Processing.

Efficient Temporal Join Processing Using Indices.
We examine the problem of processing temporal joins in the presence of indexing schemes. Previous work on temporal joins has concentrated on non-indexed relations which were fully scanned. Given the large data volumes created by the ever increasing time dimension, sequential scanning is prohibitive. This is especially true when the temporal join involves only parts of the joining relations (e.g., a given time interval instead of the whole timeline). Utilizing an index becomes then beneficial as it directs the join to the data of interest. We consider temporal join algorithms for three representative indexing schemes, namely a B+-tree, an R*-tree and a temporal index, the Multiversion B+-tree (MVBT). Both the B+-tree and R*-tree result in simple but not efficient join algorithms because neither index achieves good temporal data clustering. Better clustering is maintained by the MVBT through record copying. Nevertheless, copies can greatly affect the correctness and effectiveness of the join algorithms. We identify these problems and propose efficient solutions and optimizations. An extensive comparison of all index based temporal joins, using a variety of datasets and query characteristics shows that the MVBT based join algorithms are consistently faster. In particular the link-based algorithm has the most robust behavior. In our experiments it showed a ten-fold improvement over the R*-tree joins while it was between six and thirty times faster than the B+-tree joins. 1
Efficient Aggregation over Objects with Extent.
We examine the problem of efficiently computing sum/count/avg aggregates over...
Index Based Processing of Semi%2DRestrictive Temporal Joins.
Temporal joins are important but very costly operations. While a temporal join can involve the whole time (and/or key) domain, we consider the more general case where the join is defined by some time-key rectangle from the whole space (i.e., when the user is interested in joining portions of the –usually large – temporal data). In the most restrictive join, objects (within this rectangle) are joined together based on key equality and interval intersection. This paper concentrates on semi-restrictive joins, i.e., when either the key equality (equi-join) or the interval intersection (timejoin) predicates are used. Given the large relations created by the ever increasing time dimension, we assume that each temporal relation is indexed and examine efficient ways to process semi-restrictive temporal joins. Utilizing an index is helpful since it directs the join towards the objects that are within the time-key rectangle. A straightforward approach is to perform an unsynchronized join. An index selection query on each relation identifies all objects within the time-key rectangle which are then joined. Although simple, this approach ignores the data distribution in the other relation. Instead, in a synchronized join, both indices are concurrently traversed as the join is computed. Synchronized semi-restrictive join algorithms can be performed utilizing traditional indices like B+-trees or R-trees. The drawback of this approach is that traditional indices do not achieve good temporal data clustering. Better clustering is achieved by temporal indices through record copying. Nevertheless, record copies can greatly affect the correctness and effectiveness of join performance. In this paper we introduce correct and efficient algorithms for performing semi-restrictive temporal joins using temporal indices. An extensive experimental comparison shows that the newly proposed algorithms have the best performance. While the paper concentrates on using the Multiversion B+-tree, our algorithms apply equally to other efficient tree-based temporal indices.

Efficient Structural Joins on Indexed XML Documents.
Queries on XML documents typically combine  selections on element contents, and, via path  expressions, the structural relationships between  tagged elements. Structural joins are  used to find all pairs of elements satisfying the  primitive structural relationships specified in  the query, namely, parent child and ancestor  descendant relationships. Efficient support for  structural joins is thus the key to efficient  implementations of XML queries. Recently  proposed node numbering schemes enable the  capturing of the XML document structure us-  ing traditional indices (such as B+-trees or  R-trees). This paper proposes efficient struc-  tural join algorithms in the presence of tag  indices. We first concentrate on using B+-  trees and show how to expedite a structural  join by avoiding collections of elements that  do not participate in the join. We then intro-  duce an enhancement (based on sibling pointers)  that further improves performance. Such  sibling pointers are easily implemented and  dynamically maintainable. We also present a  structural join algorithm that utilizes R-trees.

Efficient Computation of Temporal Aggregates with Range Predicates.
A temporal aggregation query is an important but costly operation for applications that maintain timeevolving  data (data warehouses, temporal databases, etc.). Due to the large volume of such data, performance  improvements for temporal aggregation queries are critical. In this paper we examine techniques to compute  temporal aggregates that include key-range predicates (range temporal aggregates). In particular we concentrate  on SUM, COUNT and AVG aggregates. This problem is novel; to handle arbitrary key ranges, previous  methods would need to keep a separate index for every possible key range. We propose an approach based  on a new index structure called the Multiversion SB-Tree, which incorporates features from both the SB-Tree  and the Multiversion B-Tree, to handle arbitrary key-range temporal SUM, COUNT and AVG queries. We  analyze the performance of our approach and present experimental results that show its efficiency.  1 
Storing and Querying Multiversion XML Documents using Durable Node Numbers.
Managing multiple versions of XML documents represents an important problem for many traditional applications, such as software configuration control, as well as new ones, such as link permanence of web documents. Research on managing multiversion XML documents seeks to provide efficient and robust techniques for storing, retrieving and querying such documents. In this paper, we present a novel approach to version management that achieves these objectives by a scheme based on Durable Node Numbers and timestamps for the elements of XML documents. We first present efficient storage and retrieval techniques for multiversion documents. Then, we explore the indexing and clustering strategies needed to assure efficient support for complex queries on content and on document evolution. 1
